Palindrome partitioning II

Time: O(N^2); Space: O(N^2); hard

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example 1:

Input: s = “aab”

Output: 1

Explanation:

  • The palindrome partitioning [“aa”,“b”] could be produced using 1 cut.

Example 2:

Input: s = “a”

Output: 0

Explanation:

  • “a” is already a palindrome, no need to split.

[2]:

class Solution1(object):
    """
    Time: O(N^2)
    Space: O(N^2)
    """
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        lookup = [[False for j in range(len(s))] for i in range(len(s))]
        mincut = [len(s) - 1 - i for i in range(len(s) + 1)]

        for i in reversed(range(len(s))):
            for j in range(i, len(s)):
                if s[i] == s[j]  and (j - i < 2 or lookup[i + 1][j - 1]):
                    lookup[i][j] = True
                    mincut[i] = min(mincut[i], mincut[j + 1] + 1)

        return mincut[0]

[3]:

sol = Solution1()

s = "aab"
assert sol.minCut(s) == 1

s = "a"
assert sol.minCut(s) == 0